Existing software applications enable the creation of video compositions involving multiple videos combined with one another. In one example, a user creates a composition that plays five video one after another by specifying the positions of the videos on a timeline. In another example, portions of one or more of the videos are blended at video transitions by placing videos on different, partially-overlapping tracks on such a timeline. While these video composition creation applications provide numerous features to enable the creation of video compositions, the applications generally do not facilitate the user's finding and selection of videos to include in such compositions. Video professionals and enthusiasts accumulate large volumes of video data over time. When working on a composition project, visually scanning this tremendous amount of data to find relevant videos is a difficult task. For example, consider a videographer planning to build a wedding portfolio for a client. For this project, he would need to manually review each video in his collection to check if it is about a wedding or not and then filter out relevant videos. This manual search consumes a considerable amount of time, delaying the actual creative work. One way to attempt to address this burden is to manually apply relevant tags to all of the videos in the video collection so that quicker tag-based searches can be used. However, tagging all videos in a video collection can be extremely burdensome and requires consistent book-keeping of new videos to apply relevant tags on an ongoing basis. Thus, manual tagging methods are generally too burdensome and time consuming, especially for large video collections, to be practical.